/**
 * 
 */
package tree;

/**
 * @author xyyi
 *http://collabedit.com/87hmh
 *
 */
public class IntervalTree {

	private IntervalNode root;
	private int begin = 0;
	private int end = 0;

	/**
	 * 
	 */
	public IntervalTree(int begin, int end) {
		this.begin = begin;
		this.end = end;
		root = build(begin, end);
	}

	public int query(int key) {
		return query(root, key);
	}

	public void insert(int key) {
		insert(root, key);
	}

	private int query(IntervalNode root, int key) {
		if (root == null)
			return 0;
		else if (key < root.begin)
			return root.size;
		else if (key >= root.end)
			return 0;

		return query(root.left, key) + query(root.right, key);

	}

	private void insert(IntervalNode root, int key) {
		if (root == null)
			return;

		if (key == root.end && key == root.begin)
			root.size = 1;
		else if (key <= root.end && key >= root.begin) {
			root.size++;
			if (key <= (root.begin + root.end) / 2)
				insert(root.left, key);
			else
				insert(root.right, key);
		}
	}

	private IntervalNode build(int begin, int end) {
		if (begin > end)
			return null;
		else if (begin == end)
			return new IntervalNode(begin, end);

		IntervalNode root = new IntervalNode(begin, end);
		root.left = build(begin, (begin + end) / 2);
		root.right = build((begin + end) / 2 + 1, end);
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 4, 2, 1, 3 };
		IntervalTree it = new IntervalTree(1, 4);
		int ret = 0;
		for (int i = 0; i < 4; i++) {
			ret += it.query(a[i]);
			it.insert(a[i]);
		}

		System.out.printf("%d \n", ret);
	}

}

class IntervalNode {
	int begin, end, size;
	IntervalNode left = null;
	IntervalNode right = null;

	public IntervalNode(int begin, int end) {
		this.begin = begin;
		this.end = end;
		size = 0;
	}
}